/*
 花朵数
一个N位的十进制正整数，如果它的每个位上的数字的N次方的和等于这个数本身，则称其为花朵数。
例如：
当N=3时，153就满足条件，因为 1^3 + 5^3 + 3^3 = 153，这样的数字也被称为水仙花数
（其中，“^”表示乘方，5^3表示5的3次方，也就是立方）。
当N=4时，1634满足条件，因为 1^4 + 6^4 + 3^4 + 4^4 = 1634。
当N=5时，92727满足条件。
实际上，对N的每个取值，可能有多个数字满足条件。
程序的任务是：求N=21时，所有满足条件的花朵数。注意：这个整数有21位，它的各个位数字的21次方之和正好等于这个数本身。

如果满足条件的数字不只有一个，请从小到大输出所有符合条件的数字，每个数字占一行。
因为这个数字很大，请注意解法时间上的可行性。要求程序在3分钟内运行完毕。

-----------------------------------------------------------------------
解题思路：21位的花朵数，如果一个一个的暴力搜索，将会耗费大量时间，不可行。
这里使用了一些技巧：将0~9这10个数进行组合（每个数都可多次使用），从而形成一个21位的数，并记录0~9这十个基数分别
的使用次数，然后将这21个数分别求21次方并累加求和（这里使用了java的BigInteger数组来预先计算并存储0~9的21次方的结果），
然后判断求出的和中0~9每个数字的使用次数是否和搜索出来的组合相同，若相同则这个数就是符合条件的花朵数。

																————友缘

【程序运行参考结果】

128468643043731391252
449177399146038697307
 */
package com.yuan.algorithms.arithmetic_1;

import java.math.BigInteger;

public class 递归_21位花朵数 {

	static BigInteger[] base = new BigInteger[10];//预先保存每个数的21次方
	public static void main(String[] args) {
		int[] s = new int[10];//记录0~9每个数的使用次数
		for (int j = 0; j < 10; j++) {
			base[j] = calcu_21(j);
		}
		f(s, 0, 21);
		//System.out.println(base[9].toString().length());
	}
	/**
	 * 
	 * @param s 用来记录0~9的使用次数
	 * @param k 当前组合的位置
	 * @param sum 组成的数的位数（21位）的剩余位数
	 */
	private static void f(int[] s, int k, int sum) {
		//递归的出口
		if (sum==0) {
			test(s);//调用test方法测试组合成的数是否是花朵数
			return;
		}
		//搜索到最后一位数，其的值就是剩下的能被使用的次数，直接进行赋值
		if (k==s.length-1) {
			s[k] = sum;
			f(s, k+1, 0);
			s[k] = 0;//回溯
			return;
		}
		
		//利用递归进行组合
		for (int i = 0; i <= sum; i++) {
			s[k] = i; 
			f(s, k+1, sum-i);//记录各个数使用次数的数组，当前位置+1，能使用的次数sum减去已使用的次数i传入下层递归
			s[k] = 0; //回溯
		}
	}
	
	/**
	 * 测试用数组s记录的每个数的使用次数是否能组合成花朵数
	 * @param s 包含0~9使用次数的数组
	 */
	private static void test(int[] s) {
		BigInteger result = new BigInteger("0");
		//用接收的数据来求和
		for (int i = 0; i < s.length; i++) {
			result = result.add(base[i].multiply(BigInteger.valueOf(s[i])));
		}
		String x = result.toString();
		//如果得到的结果的位数不是21位，则不是花朵数，返回。
		if (x.length()!=21) {
			return;
		}
		int[] temp = new int[10];//临时记录结果中各个数字出现的次数
		for (int i = 0; i < x.length(); i++) {
			temp[x.charAt(i)-'0']++;
		}
		//对比结果和搜索的值中各个数的使用次数是否相符，若不相符，则不是花朵数，返回。
		for (int i = 0; i < s.length; i++) {
			if (s[i]!=temp[i]) {
				return;
			}
		}
		//是花朵数，输出结果
		System.out.println(x);
	}

	/**
	 * 求n的21次方
	 * @param n 目标数
	 * @return n的21次方
	 */
	private static BigInteger calcu_21(int n) {
		BigInteger a = new BigInteger("1");
		for (int i = 0; i < 21; i++) {
			a = a.multiply(BigInteger.valueOf(n));//求n的21次方
		}
		return a;
	}

}
